package cxydmmszl.tmp.t4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * <li style="color: red;">Prob</li>
 * 两个有序数组间相加和的 TopK 问题
 * <li style="color: green;">Desc</li>
 * 给定两个有序数组 arr1 和 arr2，再给定一个整数 k，返回来自 arr1 和 arr2 的
 * 两个数相加和最大的前 k 个，两个数必须分别来自两个数组，按照降序输出。
 * <br/><br/>[要求]<br/>
 * 时间复杂度为 O(klogk)
 * <br/><br/>备注：<br/>
 * 1⩽N⩽10^5<br/>
 * 0⩽arr1[i], arr2[i]⩽10^9<br/>
 * 保证 1⩽K⩽2N
 * <li style="color: green;">Input</li>
 * 第一行三个整数 N, K 分别表示数组 arr1, arr2 的大小，以及需要询问的数
 * 接下来一行N个整数，表示arr1内的元素
 * 再接下来一行N个整数，表示arr2内的元素
 * <li style="color: green;">Output</li>
 * 输出 K 个整数表示答案
 * <li style="color: blue;">Link</li> CD83
 *
 * @author habitplus
 * @since 2021-11-02 14:23
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (IOException e) {
            throw new RuntimeException("Input is invalid!");
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int k = nextInt();
        int[] arr1 = new int[n];
        int[] arr2 = new int[n];
        for (int i = 0; i < n; i++) arr1[i] = nextInt();
        for (int i = 0; i < n; i++) arr2[i] = nextInt();

        int[] res = topKFromTwoArr(arr1, arr2, k);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            sb.append(res[i]).append(" ");
        }
        System.out.println(sb.toString());
    }

    private static int[] topKFromTwoArr(int[] arr1, int[] arr2, int k) {
        if (arr1 == null || arr2 == null
                || arr1.length < 1 || arr1.length != arr2.length
                || k < 1 || k > arr1.length * arr2.length)
            return new int[0];

        // 大顶堆
        PriorityQueue<Node> maxHeap = new PriorityQueue<>(new Comparator<Node>() {
            public int compare(Node o1, Node o2) {
                return o2.value - o1.value;
            }
        });

        HashSet<String> set = new HashSet<>();
        int[] res = new int[k];
        int i = 0;
        int i1 = arr1.length - 1;
        int i2 = arr2.length - 1;

        maxHeap.add(new Node(i1, i2, arr1[i1] + arr2[i2]));
        set.add(String.valueOf(i1 + "_" + i2));
        while (i != k) {
            Node cur = maxHeap.poll();
            res[i++] = cur.value;
            i1 = cur.i1;
            i2 = cur.i2;
            if (!set.contains(String.valueOf((i1 - 1) + "_" + i2))) {
                set.add(String.valueOf((i1 - 1) + "_" + i2));
                maxHeap.add(new Node(i1 - 1, i2, arr1[i1 - 1] + arr2[i2]));
            }

            if (!set.contains(String.valueOf(i1 + "_" + (i2 - 1)))) {
                set.add(String.valueOf(i1 + "_" + (i2 - 1)));
                maxHeap.add(new Node(i1, i2 - 1, arr1[i1] + arr2[i2 - 1]));
            }
        }
        return res;
    }

    public static class Node {
        public int i1;
        public int i2;
        public int value;

        public Node(int i1, int i2, int value) {
            this.i1 = i1;
            this.i2 = i2;
            this.value = value;
        }
    }
}
